package java_0220.leetcode;

import java.util.*;

/**
 * 二叉树的层序遍历
 * 用二维数组保存：一层用一个小集合存储，最后大集合存储所有层
 */
public class Num102_LevelOrder {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret=new ArrayList<>();
        if(root==null){
            return ret;
        }
        //借助队列实现遍历过程-双端队列
        Deque<TreeNode> queue=new LinkedList<>();
        queue.offer(root);//根节点入队
        while(!queue.isEmpty()){
            //使用一个temp数组保存当前层的元素
            List<Integer> temp=new ArrayList<>();
            //取出当前层所有元素添加进temp中
            int size= queue.size();//当前层元素的个数
            for (int i = 0; i < size; i++) {
                TreeNode cur=queue.poll();//依次从队列中取队首元素
                temp.add(cur.val);//队首元素的值添加到当前层中
                if(cur.left!=null){
                    queue.offer(cur.left);//cur左树不为空就将左树入队
                }
                if(cur.right!=null){
                    queue.add(cur.right);
                }
            }
            ret.add(temp);
        }
        return ret;
    }
}
